package com.xinwei.leetcode.二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
public class _235_二叉搜索树的最近公共祖先 {
    // 先是二叉搜索树中的搜索
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> list = new ArrayList<>();
        searchTreeNode(root, p, list);
        ArrayList<TreeNode> list1 = new ArrayList<>();
        searchTreeNode(root, q, list1);
        for (int i = 0; i < Math.min(list.size(), list1.size()); i++) {
            System.out.print(list.get(i).val + " ");
            System.out.print(list1.get(i).val + " ");
            if (list.get(i).val != list1.get(i).val) {
                return list.get(i - 1);
            }
        }
        return list.get(Math.min(list.size(), list1.size()));
    }

    private void searchTreeNode(TreeNode node, TreeNode p, List<TreeNode> list) {
        while (node.val != p.val) {
            list.add(node);
            if (p.val > node.val) {
                node = node.right;
            }else {
                node = node.left;
            }
        }
        list.add(p);
    }


    // 改进：在搜索的途中遇见不同就返回
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node.val != p.val && node.val != q.val) {
            if ((p.val - node.val) * (q.val - node.val) < 0) {
                return node;
            }
            if (p.val > node.val) {
                node = node.right;
            }else {
                node = node.left;
            }
        }
        if (node.val != p.val) return p;
        if (node.val != q.val) return q;
        return root;
    }
}
